#include <stdio.h>
#include <stdlib.h>

typedef struct DNode    //双向链表结点结构体
{
    int data;   //数据域
    struct DNode *prior;    //前驱结点指针
    struct DNode *next;     //后继结点指针
} DNode, *DLinkList;    //双向链表类型定义
 
DLinkList CreateDLinkList() //创建双向链表头结点
{
    DLinkList L = (DLinkList)malloc(sizeof(DNode));
    L->prior = NULL;
    L->next = NULL;
    return L;
}

// 用数组创建双向链表（尾插法）
void CreateListFromArray(DLinkList L, int arr[], int n) 
{
    DNode *tail = L; // 尾指针，初始指向头结点
    
    for (int i = 0; i < n; i++) {
        DNode *newNode = (DNode *)malloc(sizeof(DNode));
        newNode->data = arr[i];
        newNode->prior = tail;
        newNode->next = NULL;
        
        tail->next = newNode;
        tail = newNode; // 更新尾指针
    }
}

//在双向链表L的第pos个位置插入数据data的结点
int insertList(DLinkList L, int pos, int data)  
{
    DNode *p = L;   //指向头结点
    int j = 0;  
    
    // 寻找第pos-1个结点
    while (p != NULL && j < pos - 1)       
    {
        p = p->next;    //指向下一个结点
        j++;    
    }
    
    if (p == NULL)   //pos值不合法
        return 0;

    DNode *s = (DNode *)malloc(sizeof(DNode));//生成新结点
    s->data = data;//将data赋值给新结点的数据域
    
    // 插入新节点
    s->next = p->next;//将p的后继结点赋值给s的后继指针
    s->prior = p;//将p赋值给s的前驱指针
    
    if (p->next != NULL)    
        p->next->prior = s;
    p->next = s;
    
    return 1;   
}

//删除双向链表L的第pos个位置的结点
int deleteList(DLinkList L, int pos)
{
    DNode *p = L;   //指向头结点
    int j = 0;  
    
    // 寻找第pos-1个结点
    while (p != NULL && j < pos - 1)   
    {
        p = p->next;    //指向下一个结点
        j++;    
    }
    
    if (p == NULL || p->next == NULL) //pos值不合法
        return 0;

    DNode *q = p->next; //指向被删除结点
    p->next = q->next;  //将q的后继结点赋值给p的后继指针
    
    if (q->next != NULL)
        q->next->prior = p; //将p赋值给q的后继结点的前驱指针
    
    free(q);   //释放被删除结点的空间
    return 1;   
}

//在双向链表L中查找值为data的结点
DNode* searchList(DLinkList L, int data) 
{
    DNode *p = L->next; //指向第一个结点
    while (p != NULL && p->data != data) //寻找值为data的结点
        p = p->next; //指向下一个结点
    return p;   //返回查找结果，找到返回结点指针，否则返回NULL
}

// 显示双向链表内容（正向）
void displayList(DLinkList L) 
{
    DNode *p = L->next; //指向第一个结点
    printf("双向链表内容(正向): ");
    while (p != NULL)   //遍历链表
    {
        printf("%d ", p->data); //输出结点数据
        p = p->next; //指向下一个结点
    }
    printf("\n");
}

// 显示双向链表内容（反向）
void displayListReverse(DLinkList L) 
{
    if (L->next == NULL) {
        printf("链表为空\n");
        return;
    }
    
    // 找到最后一个节点
    DNode *p = L->next;
    while (p->next != NULL) {
        p = p->next;
    }
    
    printf("双向链表内容(反向): ");
    while (p != L)   //遍历链表直到头结点
    {
        printf("%d ", p->data); //输出结点数据
        p = p->prior; //指向前一个结点
    }
    printf("\n");
}

// 获取链表长度
int getLength(DLinkList L) {
    int length = 0;
    DNode *p = L->next;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    return length;
}

// 销毁链表
void destroyList(DLinkList L) {
    DNode *p = L->next;
    while (p != NULL) {
        DNode *temp = p;
        p = p->next;
        free(temp);
    }
    free(L); // 释放头结点
}

int main(){
    DLinkList L = CreateDLinkList();//创建双向链表头结点
    int arr[] = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);//数组长度

    //用数组创建链表
    CreateListFromArray(L, arr, n);
    printf("初始链表:\n");
    displayList(L);
    displayListReverse(L);
    printf("链表长度: %d\n\n", getLength(L));

    //插入元素
    insertList(L, 3, 25);
    printf("插入元素25到位置3后:\n");
    displayList(L);
    displayListReverse(L);
    printf("链表长度: %d\n\n", getLength(L));

    //删除元素
    deleteList(L, 4);
    printf("删除位置4的元素后:\n");
    displayList(L);
    displayListReverse(L);
    printf("链表长度: %d\n\n", getLength(L));

    //查找元素
    DNode *foundNode = searchList(L, 30);
    if (foundNode != NULL)
        printf("找到元素: %d\n", foundNode->data);
    else
        printf("元素30未找到\n");
    
    // 测试查找不存在的元素
    foundNode = searchList(L, 100);
    if (foundNode != NULL)
        printf("找到元素: %d\n", foundNode->data);
    else
        printf("元素100未找到\n");
    
    // 销毁链表
    destroyList(L);
    
    return 0;
}